package com.ting.test.algorithms.贪心算法;

import java.util.PriorityQueue;

/**
 * 一块金条切成两半，是需要花费和长度数值一样的铜板的。
 * 比如长度为20的金条，不管怎么切，都要花费20个铜板。 一群人想整分整块金条，怎么分最省铜板?
 * <p>
 * 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。
 * <p>
 * 如果先把长度60的金条分成10和50，花费60; 再把长度50的金条分成20和30，花费50;一共花费110铜板。
 * 但如果先把长度60的金条分成30和30，花费60;再把长度30金条分成10和20， 花费30;一共花费90铜板。
 * 输入一个数组，返回分割的最小代价。
 */
public class 金条切分问题 {

    public static void main(String[] args) {
        int[] arr = new int[]{10, 20, 30};
        int cost = process(arr);
        System.out.println(cost);

    }

    private static int process(int[] arr) {
        PriorityQueue<Integer> queue = new PriorityQueue();
        for (int data : arr) {
            queue.add(data);
        }
        int cost = 0, first = 0, second = 0, sum = 0;

        while (queue.size() > 1) {
            first = queue.poll();
            second = queue.poll();
            sum = first + second;
            while (!queue.isEmpty() && queue.peek() < sum) {
                queue.poll();
            }
            queue.add(sum);
            cost+= sum;
        }


        return cost;
    }
}
